# LeetCode 673、最长递增子序列的个数
# 一、题目描述
给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。
注意 这个数列必须是 严格 递增的。
示例 1:
输入: [1,3,5,4,7] 输出: 2 解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。
示例 2:
输入: [2,2,2,2,2] 输出: 5 解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。
提示:
1 <= nums.length <= 2000-10^6 <= nums[i] <= 10^6
# 二、题目解析
# 三、参考代码
# 1、Java 代码
public class Solution {
public int findNumberOfLIS(int[] nums) {
int n = nums.length;
// LIS : 最长递增子序列
// 设置数组 dp，用来存储 nums 中以每个元素结尾的最长递增序列的长度
// dp[0] 表示以 nums[0] 结尾的 LIS 的长度
// dp[1] 表示以 nums[1] 结尾的 LIS 的长度
// dp[i] 表示以 nums[i] 结尾的 LIS 的长度
int[] dp = new int[n];
// count[i] : 以 nums[i] 为结尾的 LIS 的个数
int[] count = new int[n];
// 初始化
Arrays.fill(dp, 1);
Arrays.fill(count, 1);
// 设置一个变量用来存储最长递增序列的结果
int maxLength = 1;
// 从 0 开始，直到 dp.length ，往 dp 里面填充结果
for (int i = 0; i < n; i++) {
// 对于 dp[i] 来说，在 nums 中从 0 到 i - 1 都是在 i 的前面的
// 比如 nums 为 [1,5,2,5,3,7,2]
// 此时 i 为 3，那么 1,5,2 这些数字都在索引位置为 3 的前面
// 从 0 遍历到 i - 1，就可以从这些数字中选出小于 i 的数字
for (int j = 0; j < i; j++) {
// 1、如果 nums[i] <= nums[j]
// nums[i] 无法延伸到 nums[j] 的后面，形成新的递增序列
// 于是，跳过当前的 j 继续查看下一个 j
if (nums[i] <= nums[j]) {
continue;
}
// 2、否则，来到这里，说明 nums[i] > nums[j]
// nums[i] 可以接到 nums[j] 的后边形成新的递增序列
// 索引 0 1 2 3 4 5 6
// nums 为 [ 1, 5, 2, 5, 3, 7, 2 ]
// 此时 i 为 3，那么 1,5,2 这些数字都在索引位置为 3 的前面
// 1、从这些数字中选出小于 nums[i] 的数字
// 2、小于 nums[i] 的那些数字是 1 , 2 ，在之前都已经计算过以 1 或者 2 结尾的最长递增序列的长度
// 并且这个结果存放在 dp[j] 中
// 如果数字为 1，那么此时 j 为 0，dp[0] 存放了以 1 结尾的最长递增序列的长度
// 如果数字为 2，那么此时 j 为 2，dp[2] 存放了以 2 结尾的最长递增序列的长度
// 3、如果发现此时 dp[i] 小于了 dp[j] + 1
// 4、说明此时 dp[i] 中的值就不是以 nums[i] 结尾的最长递增序列的长度
// 需要更新 dp[i]
// 最长递增子序列的长度增加了
if (dp[i] < dp[j] + 1) {
// 更新 dp[i]
dp[i] = dp[j] + 1;
// count[i] 就是 count[j]
// 即有多少这样的 j ， 就可以找到多少个以 nums[i] 为结尾的 LIS 的个数
count[i] = count[j];
// 如果 dp[i] == dp[j] + 1
// 说明最长递增子序列的长度并没有增加，但是出现了长度一样的情况
// 此时 nums[i] 还没有添加到 nums[j] 的后边
// 以 nums[i] 为结尾的 LIS 的长度已经是 dp[j] + 1
// 以 nums[i] 为结尾的 LIS 的个数已经是 count[i]
// 那么把 nums[i] 加到 nums[j] 之后
// LIS 的长度不变，即 dp[i] 不需要更新
// LIS 包含了 nums[j]
// 有了 count[j] 个 LIS 的个数
// 总的 count[i] 更新为 count[i] += count[j]
// 比如下边的例子
// i
// 1 2 6 5 4 9
// j
// 此时 i 遍历到 9 ，j 遍历到 4
// 在 j 遍历 4 之前，要先遍历 4 之前的 1 2 6 5
// 在遍历到 6 的时候， dp[i] 就应该更新为 4 （ 1 2 6 9 这个 LIS 的长度 ）
// 在遍历完 5 的时候，这个时候的 【count[i] 为 2】
// (1 2 6 9 和 1 2 5 9 这两个 LIS)
// 遍历到 4 的时候
// dp[j] = 3 ( 1 2 4 的长度)，count[j] = 1 (就只有 1 2 4 这一个 LIS)
// 此时满足 dp[j] + 1 = 3 + 1 = 4 == dp[i]
// 这个时候，不需要更新 dp[i]，需要更新 count[i] ，【count[i] 已经是 2】
// 也就是不包含 4 的 1 2 6 9 和 1 2 5 9
// 如果把 nums[i] 也就是 9 放到 nums[j] 也就是 4 之后
// count[i] 就会多了一个包含 4 的 LIS ，也就是 1 2 4 9,
// 所以要 count[i] += count[j]
// 以 nums[i] 为结尾的 LIS 的个数个数为 3
// （1 2 6 9， 1 2 5 9 和 1 2 4 9 这 3 个 LIS ）
} else if (dp[i] == dp[j] + 1) {
// 更新 count[i]
count[i] += count[j];
}
}
// 记录最长递增子序列的最大长度 maxLength
maxLength = Math.max(maxLength, dp[i]);
}
// 初始化结果
int result = 0;
// 遍历 dp 数组
for (int i = 0; i < n; i++) {
// 最长递增子序列的长度是 maxLength
if (dp[i] == maxLength) {
// 把所有 dp[i] == maxLength 的那个 i 处对应的 count 进行累加
result += count[i];
}
}
// 返回结果
return result;
}
}
# **2、**C++ 代码
# 3、Python 代码
class Solution:
def findNumberOfLIS(self, nums: List[int]) -> int:
n = len(nums)
# LIS: 最长递增子序列
# 创建一个数组dp，用于存储以每个元素结尾的最长递增序列的长度
dp = [1] * n
# count[i]: 以nums[i]为结尾的LIS的个数
count = [1] * n
# 初始化
maxLength = 1
# 从0开始，填充dp数组
for i in range(n):
for j in range(i):
if nums[i] <= nums[j]:
continue
if dp[i] < dp[j] + 1:
dp[i] = dp[j] + 1
count[i] = count[j]
elif dp[i] == dp[j] + 1:
count[i] += count[j]
maxLength = max(maxLength, dp[i])
result = 0
for i in range(n):
if dp[i] == maxLength:
result += count[i]
return result